package 剑指offer;

public class _10_1斐波那契数列 {
     public static void main(String[] args) {
    	 System.out.println(fib2(45));
	}
     /**
      * 
      *@time 2020年12月9日下午10:33:26
      * 
      *@param n
      *@returnint
      *
      *@see
      */
     public static int fib2(int n) {
     	if(n==0||n==1)
     	  return n;
     	int dp[]=new int[n+1];
     	dp[1]=1;
     	for(int i=2;i<=n;i++) {
     		dp[i]=dp[i-1]+dp[i-2];
     		dp[i]%=1000000007;
     	}
     	return dp[n];
     }
     /**
      * 
      *@time 2020年12月9日下午10:33:43
      * 
      *@param n
      *@return int
      *
      *@see 
      *n   f(n)初始是：
      *0    0<-a
      *1    1<-b
      *1    1<-sum
      *----n=1----
      *0	0
      *1	1<-a
      *2 	1<-b
      *3	2<-sum
      *------n=2-----
      *0    0 
      *1 	1
      *2	1<-a
      *3	2<-b,sum
      *4	3
      *   
      */
     public static int fib3(int n) {
    	 int a=0,b=1,sum=0;
    	 for(int i=0;i<n;i++) {
    		 sum=a+b;
    		 a=b;
    		 b=sum%1000000007;
    	 }
    	 return sum;
     }
}
/**
 * 
 * @author 兰伟朋
 *@time 2020年12月9日下午9:36:48
 *@see
 *F(0) = 0,   F(1) = 1
 *F(N) = F(N - 1) + F(N - 2), 其中 N > 1.
 */
class Solution {
	/**
	 * 
	 *@time 2020年12月9日下午10:00:30
	 * 
	 *@param n
	 *@returnint
	 *
	 *@see 直接简单的实现所耗费的时间复杂度太久了O(2^n)的时间复杂度
	 */
    public int fib1(int n) {
    	if(n==0||n==1)
    		return n;
    	else return fib1(n-1)+fib1(n-2);
					
    }
/**
 * 
 *@time 2020年12月9日下午10:02:10
 * 
 *@param n
 *@returnint
 *
 *@see 使用动态规划来实现 时间复杂度降低到O(n)
 */
    public int fib2(int n) {
    	if(n==0||n==1)
    	  return n;
    	int dp[]=new int[n+1];
    	for(int i=2;i<=n;i++) {
    		dp[i]=dp[i-1]+dp[i-2];
    	}
    	return dp[n];
    }
}